package algorithm.shipinke;


import java.util.PriorityQueue;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/cbe887812d3041669fc93a0cf5235f63?orderByHotValue=1&amp;mutiTagIds=592&amp;page=1&amp;onlyReference=false
 * 来源：牛客网
 *
 * 给定两个整数W和K，W代表你拥有的初始资金，K代表你最多可以做K个项目。再给定两个长度为N的正数数组costs[]和profits[]，
 * 代表一共有N个项目，costs[i]和profits[i]分别表示第i号项目的启动资金与做完后的利润(注意是利润，如果一个项目的启动资金为10，利润为4，代表该项目最终的收入为14)。
 * 你不能并行只能串行地做项目，并且手里拥有的资金大于或等于某个项目的启动资金时，你才能做这个项目。该如何选择做项目，能让你最终的收益最大？返回最后能获得的最大资金
 * [要求]
 * 时间复杂度为 O(klogn)，空间复杂度为 O(n)
 *
 * 输入
 * 3 2
 * cost   = [5, 4, 1, 2]
 * profit = [3, 5, 3, 2]
 *
 * 输出
 * 11
 *
 *
 * 说明
 * 初始资金为3，最多做两个项目，每个项目的启动资金与利润见costs和profits。最优选择为：先做2号项目，做完之后资金增长到6,。
 * 然后做1号项目，做完之后资金增长到11。其他的任何选择都不会比这种选择好，所以返回11
 */

public class NowCoder {
    public int getRes(int[] cost, int[] profit , int W, int k){
        // 注意:对于所有的项目而言,两个堆中元素是互补的,即交集为空,并集为所有项目
        // 存放门槛太高暂时做不了的项目,最小堆
        PriorityQueue<int[]> pqCost = new PriorityQueue<>((o1, o2) -> o1[1]-o2[1]);
        // 存放可以做的项目,最大堆
        PriorityQueue<int[]> pqProfit = new PriorityQueue<>((o1, o2) -> o2[1]-o1[1]);

        // 初始化
        for (int i = 0; i < profit.length; i++) {
            // 做的了的先放进pqProfit
            if (W >= cost[i]) {
                pqProfit.add(new int[]{i, profit[i]});
            }
            // 做不了的放到pqCost
            else {
                pqCost.add(new int[]{i, cost[i]});
            }
        }

        int times = 0;
        while (!pqProfit.isEmpty() && times < k) {
            while (!pqCost.isEmpty() && W >= pqCost.peek()[1]) {
                int[] poll = pqCost.poll();
                pqProfit.add(new int[]{poll[0], profit[poll[0]]});
            }
            int[] poll = pqProfit.poll();
            W += poll[1];
            times++;
        }
        return W;
    }

    public static void main(String[] args) {
        NowCoder nowCoder = new NowCoder();
        System.out.println(nowCoder.getRes(new int[]{5, 4, 1, 2}, new int[]{3, 5, 3, 2}, 3, 2));
    }
}
